UUID,Universal Unique Identifier,全局唯一标识符。也叫做GUID,Global Unique Identifier。

概念都了解,全局唯一嘛,但怎么实现的?多大概率重复?JDK的UUID和PostgreSQL的UUID一样吗?带着这些问题,我们从RFC,到JDK源码、PG手册,一点点看。

本文包含以下内容:

  • UUID实现原理
  • 自己实现一个UUID
  • JDK的实现方式
  • PG的实现方式
  • 其它全局唯一ID

实现原理

老样子,要想了解一项基础技术,最好的方式是阅读一手资料。于UUID,它是RFC4122

这一节,更莫如说是对RFC的总结,毕竟规范这东西,写得太啰嗦了,全文字不说,还没有示意图。

基本特性

  • 长度128个bit位。一般通过16位十六进制字符表示,如:4cc9de16-414b-4f68-9b7e-6feeb8f629b0
  • 不需要中心管理,具有跨越时间和空间的唯一性
  • 按照本标准中的算法,支持每台机器每秒高达1000万次高分配速率

组成

理解UUID有两个重点:一是理解其组成部分;二是理解各版本对各部分的填充方式。我们先看最重要的——组成部分。

为了较为形象地展示,我画了张图。第一行是结果,第二行是十六进制说明,第三行是二进制说明。

image-20210930084244949

  • time-low:时间戳低位,占用32个bit
  • time-mid:时间戳中位,占用16个bit
  • time-high-and-version:时间戳高位+版本号,前者占12个bit,后者占4个bit,注意区分版本号是在前的
  • clock-seq-high-and-reserved:时钟序列高位+预留位。前者占6个bit,后者占2个bit,也注意他们的前后顺序
  • clock-seq-low:时间序列低位,占8个bit
  • node:节点,占用48个bit

引出新概念,time、clock-seq、node

  • time:即时间戳
  • clock-seq:当时间戳或node重复时,使用clock-seq作为附加保证唯一性
  • node:机器的节点,一般是机器的MAC地址

区分版本

注意到上面说组成时,有一个version字段。UUID是有多个版本的,目前总计5个。

版本规定了各字段的填充方式,版本2比较特殊这里忽略,其它版本如下

版本 Timestamp Clock sequence node
1 从UTC时间1582-10-15 00:00:00起,100ns的个数 第一个clock sequence应该是随机产生的
如果知道本机上一次生成UUID的clock sequence,则此次只需要在其基础上加一
如果不知道,该字段需要设置成一个随机数
MAC地址 如果没有,则使用随机数
3 命名空间+名称的MD5只的一部分 命名空间+名称的MD5只的一部分 命名空间+名称的MD5只的一部分
4 随机数的一部分 随机数的一部分 随机数的一部分
5 命名空间+名称的SHA1只的一部分 命名空间+名称的SHA1只的一部分 命名空间+名称的SHA1只的一部分

可以看到,所谓的时间戳、时钟序列、node这些字段,仅对版本1有效,其它版本填充进去的值并无逻辑意义。

如何保证唯一性

  • 对Version 1:它通过MAC地址保证空间唯一性,时间戳+序列号保证时间唯一性
  • 对Version 2:和Version 1类似,只不过会把时间戳的前4位置换为POSIX的UID或GID
  • 对Version 3、5:它纯依赖于名字保证唯一性,这就需要一个规整的命名系统:命名空间+名称
  • 对Version 4:它纯通过随机数保证唯一性,此时一个高质量的随机数发生器就显得尤为重要

Version 1生成逻辑

  1. 获取一个系统级别的全局时钟

  2. 从一个系统全局共享的的存储位置,读取上一个UUID的状态:时间戳、始终序列、node等

  3. 获取当前时间戳:从UTC时间1582-10-15 00:00:00起,100ns的个数

  4. 获取nodeid,即MAC地址

  5. 如果上一个UUID状态不稳定(不存在、nodeid与新获取的nodeid不一样),生成一个随机clock value

  6. 如果状态存在,但时间戳比当前时间戳还晚,则clock sequence自增

  7. 将新的状态保存

  8. 将上面的三个部分按照格式组成UUID

有一个bug

MAC地址直接放在nodeid中,就是一个bug,这会暴露用户的MAC地址:梅丽莎病毒制作者的位置就是这么暴露的

Version 4生成逻辑

  1. 获取一个随机数
  2. 将预留位、版本位之外的位,使用该随机数填充,填充位对应方式,参考RFC

Version 3、5生成逻辑

  1. 命名空间+名字组成字符串,使用MD5或者SHA1计算摘要
  2. 将预留位、版本位之外的位,使用该摘要填充,填充位对应方式,参考RFC

为什么时间戳从1582-10-15开始

这是公历改革到基督教日历的日期,说来话长,我也没啥兴趣去详细了解,如果需要,看看知乎吧

自己写一个UUID吧

尝试着实现了一下抽象定义和基于时间戳的版本,发现主要有几个难点:kotlin的进制转换、二进制操作等。

这是一个不能实际使用的UUID版本(实现它也不是本文的目的),仅作演示。

先是UUID的抽象定义,我们使用两个Long作为底层bit持有对象,定义各字段的set方法,主要是二进制操作。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
abstract class UUID {

companion object {

const val TIME_LOW_MASK = (0xFFFFFFFFL).shl(32)
const val TIME_MID_MASK = (0xFFFFFFFFL).shl(16)
const val VERSION_MASK = (0xFFL).shl(12)
const val TIME_HIGH_MASK = 0xFFFFFFL

const val RESERVED_MASK = (0xFL).shl(62)
const val CLOCK_SEQ_HIGH_MASK = (0xFFFL).shl(56)
const val CLOCK_SEQ_LOW_MASK = (0xFFFFL).shl(48)
const val NODE_MASK = 0xFFFFFFFFFFFFL

fun timeBasedUUID(): UUID = UUIDVersion1()

}

/**
* 高有效位们:靠右
*/
private var mostSignificantBits = 0L

/**
* 低有效位:靠左
*/
private var leastSignificantBits = 0L

fun setTimeLow(timeLow: Int) {
leastSignificantBits = leastSignificantBits.or(timeLow.toLong().shl(32).and(TIME_LOW_MASK))
}

fun setTimeMid(timeMid: Int) {
leastSignificantBits = leastSignificantBits.or(timeMid.toLong().shl(16).and(TIME_MID_MASK))
}

fun setVersion(version: Int) {
leastSignificantBits = leastSignificantBits.or(version.toLong().shl(12).and(VERSION_MASK))
}

fun setTimeHigh(timeHigh: Int) {
leastSignificantBits = leastSignificantBits.or(timeHigh.toLong().and(TIME_HIGH_MASK))
}

fun setReserved(reserved: Int) {
mostSignificantBits = mostSignificantBits.or(reserved.toLong().shl(62).and(RESERVED_MASK))

}

fun setClockSeqHigh(clockSeqHigh: Int) {
mostSignificantBits = mostSignificantBits.or(clockSeqHigh.toLong().shl(56).and(CLOCK_SEQ_HIGH_MASK))
}

fun setClockSeqLow(clockSeqLow: Int) {
mostSignificantBits = mostSignificantBits.or(clockSeqLow.toLong().shl(48).and(CLOCK_SEQ_LOW_MASK))

}

fun setNode(nodeId: Int) {
mostSignificantBits = mostSignificantBits.or(nodeId.toLong().and(NODE_MASK))

}

override fun toString(): String {
val lsbString = leastSignificantBits.toHexString()
val msgString = mostSignificantBits.toHexString()

val seg1 = lsbString.substring(0, 8)
val seg2 = lsbString.substring(8, 12)
val seg3 = lsbString.substring(12, 16)
val seg4 = msgString.substring(0, 4)
val seg5 = msgString.substring(4, 16)

return "$seg1-$seg2-$seg3-$seg4-$seg5"
}

}

然后是一个粗糙的实现类,实现Version 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class UUIDVersion1 : UUID() {

init {
// 计算time
val start = LocalDateTime.of(1582, 10, 15, 0, 0, 0, 0)
val end = LocalDateTime.now(ZoneId.of("UTC"))
val duration = Duration.between(start, end)
val time = duration.toMillis() * 10
// 计算clock seq
val clock = 0
// 获取node,我们用随机数替换
val node = Random.nextInt()

this.setTimeLow(time.toInt())
this.setTimeMid(time.shr(32).toInt())
this.setTimeHigh(time.shr(48).toInt())

this.setClockSeqHigh(clock.shr(8))
this.setClockSeqLow(clock)

this.setNode(node)

this.setVersion(0b001)
this.setReserved(0b10)
}

}

我们还可以将生成的UUID转换为JDK的UUID进行验证。

1
2
3
4
5
6
7
8
9
10
fun main() {
val uuidString = UUID.timeBasedUUID().toString()
println(uuidString)
val uuid = java.util.UUID.fromString(uuidString)
println(uuid.version())
println(uuid.variant())
println(uuid.timestamp())
println(uuid.clockSequence())
println(uuid.node())
}

能够得到如下输出

1
2
3
4
5
6
51d8c022-7dfc-1000-8000-ffffd963e9ed
1
2
138522658390050
0
281474328947181

仔细想想,这个时间戳也不一定要从1580年开始,也可以换成自定义的时间戳,完全看需求。

JDK UUID

JDK只提供Version 3和Version 4两种UUID,实现上也超级简单。

类似地,它也用两个long来组成128位,构建时直接分配位即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
/*
* The most significant 64 bits of this UUID.
*
* @serial
*/
private final long mostSigBits;

/*
* The least significant 64 bits of this UUID.
*
* @serial
*/
private final long leastSigBits;

private UUID(byte[] data) {
long msb = 0;
long lsb = 0;
assert data.length == 16 : "data must be 16 bytes in length";
for (int i=0; i<8; i++)
msb = (msb << 8) | (data[i] & 0xff);
for (int i=8; i<16; i++)
lsb = (lsb << 8) | (data[i] & 0xff);
this.mostSigBits = msb;
this.leastSigBits = lsb;
}

Version 4

1
2
3
4
5
6
7
8
9
10
11
public static UUID randomUUID() {
SecureRandom ng = Holder.numberGenerator;

byte[] randomBytes = new byte[16];
ng.nextBytes(randomBytes);
randomBytes[6] &= 0x0f; /* clear version */
randomBytes[6] |= 0x40; /* set to version 4 */
randomBytes[8] &= 0x3f; /* clear variant */
randomBytes[8] |= 0x80; /* set to IETF variant */
return new UUID(randomBytes);
}

可以看到,重点其实在Holder.numberGenerator,它的随机性决定了UUID的重复概率。而其实现SecureRandom,则涉及到另一个知识点——随机数,我们这里挖个坑,后面再探究随机数生成器到底有多随机。

1
2
3
private static class Holder {
static final SecureRandom numberGenerator = new SecureRandom();
}

Version 3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public static UUID nameUUIDFromBytes(byte[] name) {
MessageDigest md;
try {
md = MessageDigest.getInstance("MD5");
} catch (NoSuchAlgorithmException nsae) {
throw new InternalError("MD5 not supported", nsae);
}
byte[] md5Bytes = md.digest(name);
md5Bytes[6] &= 0x0f; /* clear version */
md5Bytes[6] |= 0x30; /* set to version 3 */
md5Bytes[8] &= 0x3f; /* clear variant */
md5Bytes[8] |= 0x80; /* set to IETF variant */
return new UUID(md5Bytes);
}

这个更简单,做一下MD5,修改相应的bit填入即可,它的唯一性就完全依赖于传入的name了。

PostgreSQL的UUID

根据手册描述,PG的UUID也是Version 4,即基于随机数生成。

UUID重复的概率

就是个好奇,我们能够大致算一算,UUID重复的概率有多大,其实可以归结如下。

  • 对基于时间戳的情况,node稳定时,多个节点不可能重复,而单个节点,由于有记录上一个UUID的状态,因此也不会重复。只不过有生成速率限制,以RFC的方式来说,每个节点每100ns,最多能够生成2^14=16384个UUID,换算成秒,即每秒1.6亿个。

  • 基于随机数的情况,取决于随机数生成器的质量

  • 基于名字的情况,取决于命名系统,这种情况UUID只是命名系统的延伸,应该说不会考虑UUID重复的情况,而是命名系统本身的性能

  • 128bit空间本身是否可能重复呢?用尽了就会,不过这个概率,类似流星撞地球吧。

其它全局唯一ID

最为大家熟知的恐怕就是雪花算法了吧,此外号段模式也算一个。

雪花算法(SnkwFlake)

了解了UUID Version 1的生成方式后,雪花算法就很容易理解,也是由时间戳-机器id-序列号组成,不同的是其只需要64个bit。且各字段可以根据实际需求调整bit的个数。雪花算法只是一种思想:将各位打散,再赋予不同的用途。UUID Version 1也是这种思想。

image-20210930142313559

几个需要考虑的问题

  • 时钟回拨问题:常见的方式是容忍小范围回拨,即如果当前时间戳比上一个生成的时间戳早,且在一定范围内,则依旧使用上一次的时间戳。这算一种校准方式,即回拨的这个时间差会被算到上一个时间戳的序列中,随着时间的推移,时间回拨问题会被抹平,但这段期间的生成效率会降低。
  • 机器ID的生成方式:机器ID必须是稳定的,常见的解决方式是融合MAC地址。

雪花算法和UUID差别

雪花算法得到的id依旧是64位,就是一个long,且时间戳在高位,是有序递增的。有序性,往往很重要。

一些雪花算法的实现

  • 百度UidGenerator

    它解决时钟回拨的方式,是不容忍任何回拨,直接报错

  • 美团Leaf

    可选基于雪花算法或基于号段模式两种方案。其中使用雪花算法时,依赖于Zookeeper来分配WorkerID

    它解决时钟回拨问题,和上面我们说的类似

号段模式

这并不是什么算法,而是一种数据库自增ID的用法,一次取一批ID,用完了再取,保证了唯一性,降低了数据库的访问频率。

分布式ID的选择

你看,我们已经了解了最重要的全局唯一ID生成方式,那就可以讨论这个问题:分布式ID应该用哪种呢?

UUID优点在于生成简单,唯一性好,几乎所有语言都有标准实现。缺点在于长度过长、不具有单调性,且无意义。

雪花算法优点在于具有单调性,长度适中。缺点在于需要自己实现或引入第三方库。(一说雪花算法缺点在于依赖时间,但要在跨时间上保证唯一性,除了依赖时间,就是依赖随机数,所以我认为也算不上缺点,且时间回拨不是已经有解决方式了嘛)

如果ID需要存入数据库,由于UUID的无序性,可能会使得索引重建花费较长时间,当然使用雪花算法比较好

每记选择UUID作为key,合理吗?

作为一个离线客户端软件,我们面临以下问题

  • 客户端环境千奇百怪,多平台(PC、网页、安卓、IOS等),多版本,总之,就很难信任客户端环境
  • 离线时也要能正常使用

如果使用雪花算法,会有几个问题

  • 首先,工作机器ID的确定,需要考虑的情况就会比较多,即生成算法需要调试。客户端的时间回拨,那可不就是修正就能够完事的。
  • 其次,即使有序性有了,但多个设备上传的顺序依旧无法保证,受网络、环境影响较大,依旧会造成索引重建时候较多数据的移动

如果使用UUID,其实就只有一个问题

  • 数据库存储的效率:索引重建。如果是聚簇索引,索引重建时移动的数据会很多,这对MySQL的innodb这类引擎来说可能是灾难。但是PgstgreSQL并非以B+树存储数据,所以性能损失并非想象的那么严重。具体如何,待后面详细研究一波PG的各种原理(完蛋,又挖了一个坑)

    且,即使是MySQL,依然可以解决:主键设为单调自增的number,来自客户端的UUID仅作为普通字段,在该字段创建索引,会好很多。

综上所述,使用UUID对客户端更方便,在服务端性能也算可以接受,所以说是合理的

作为佐证,我抓了一个印象笔记下类每记产品”印象清单“,它就更加直白了,id字段名为”taskGuid“,值就是UUID。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
[
{
"syncDataObject":{
"tasks":[
{
"state":1,
"ruleId":"",
"description":"",
"clientUpdatedTime":1632988316566,
"sortIndex":0,
"dueTime":1632988311635,
"operation":0,
"title":"测试",
"finishedTime":-1,
"taskGuid":"a1e4836c-4d59-409d-bf00-864d6d31cba0",
"createTime":1632988316566,
"taskListId":"default",
"reminderTime":-1,
"reminderType":0,
"taskRelatedNote":[

]
}
],
"rules":[

],
"taskLists":[

]
}
}
]

好文推荐

这篇UUID的文章写的不错,如果结合起来看,可以增进理解:冷饭新炒:理解JDK中UUID的底层实现

雪花算法呢,这篇文章看起来还行:SnowFlake

美团的Leaf,美团技术团队博客有进行说明:Leaf——美团点评分布式ID生成系统

总结

研究UUID的出发点,只是其RFC很短,仅三十多页,有效内容不到二十页。过程中却有几点意外之喜:

  • 顺着UUID的实现原理,了解到JDK的实现方式,自此,UUID于我,成了白盒;
  • 能够体会JDK不提供Version1的原因(它太依赖具体系统,而语言级别的实现,一定是要所有情况通用的,显然Version 1的通用实现,不大好办);
  • 思路发散到分布式ID,详细了解了雪花算法,它和Version 1是如此接近,却只因为将node和seq换了个位置就能够单调递增,如此相似,结果却如此不同;
  • 离线客户端用SnowFlake如何?它们看起来是大型分布式系统,实则与我们后端常说的分布式系统很不一样,这其中最大的不同是客户端环境不可控。
  • 同时,还挖了两个坑:深入研究随机数、深入研究PostgreSQL

本着输出驱动输入的方法完成本文,预期一两天,实则因思路发散花了更多时间,结果是令人满意的,因为它让我对技术,又少了一个模糊地带。

也应验了那句话:持续不断地学习,一定会给你带来惊喜。关键词是:持续不断

留言

2021-09-30

⬆︎TOP